In the morning, many students do their exercises. According to
established tradition, the students dance in the branded T-shirts. During the
first three days of the camp, schoolchildren and teachers noticed that a couple
who dances in identical T-shirts looks more aesthetically better. Therefore,
before the exercises, they decided first to put pairs of children in identical
T-shirts, and then the remaining ones. The excellent student Seryozha wanted to
know what the largest number of aesthetic pairs can be formed from everyone who
came to morning exercises.
Input. Sequence of n (n
≤ 106) positive integers, giving the color of a T-shirt (the color
is a number from 0 to 9).
Output. Print the number of
aesthetic pairs that can be made up.
|
Sample input |
Sample output |
|
0 3 6 3 0 0
1 |
2 |
counting
sort
T-shirt color is a number from 0 to 9. Let’s count the number of
T-shirts of color i in m[i]. Then, out of schoolchildren wearing
a T-shirt of color i, one can make m[i] / 2 aesthetic pairs. Then the total
number of aesthetic pairs is
m[0]
/ 2 + m[1] / 2 + … + m[9] / 2
Declare the array for counting.
int m[10];
Read the input data. Perform the counting sort. In
cell m[i] count the number of T-shirts
of color i.
while (scanf("%d", &x) == 1)
m[x]++;
In the variable res
count the number of aesthetic pairs.
res = 0;
for (i = 0; i < 10; i++)
res += m[i] / 2;
Print the answer – the required number of aesthetic
pairs.
printf("%lld\n", res);